﻿using System.Text;

namespace DataStructure;

//单链表类，具备头尾指针
public class TaiLinkList<E> : IFifoList<E>
{
    //私有的内部结点类
    private class Node
    {
        public E e;//结点中存储的元素
        public Node next;//存储下一个结点的引用

        //通过元素和下一个结点的引用创建结点
        public Node(E e, Node next)
        {
            this.e = e;
            this.next = next;
        }

        //通过元素创建结点
        public Node(E e) : this(e, null) { }

        //输出结点的信息
        public override string ToString()
        {
            return e.ToString();
        }
    }

    //头指针标识链表的头部
    private Node head;

    //尾指针标记链表尾部结点
    private Node tail;

    //链表中元素的个数
    private int N;

    //链表初始化：一个结点也没有，head和tail指向空，N为0
    public TaiLinkList()
    {
        head = null;
        tail = null;
        N = 0;
    }

    //只读属性：获取链表中元素的个数
    public int Count => N;

    //只读属性：判断链表是否为空
    public bool IsEmpty { get { return N == 0; } }

    //在链表的尾部添加元素
    public void AddLast(E e)
    {
        Node node = new(e);

        if (IsEmpty)
        {
            head = node;
            tail = node;
        }
        else
        {
            tail.next = node;
            tail = node;
        }

        N++;
    }

    //获取链表头部元素
    public E GetFirst()
    {
        if (IsEmpty)
            throw new InvalidOperationException("链表为空");

        return head.e;
    }

    //删除链表的头部元素
    public E RemoveFirst()
    {
        if (IsEmpty)
            throw new InvalidOperationException("链表为空");

        E e = head.e;

        head = head.next;
        N--;

        if (head == null)
            tail = null;

        return e;
    }

    //清空链表
    public void Clear()
    {
        head = null;
        tail = null;
        N = 0;
    }

    //打印链表
    public override string ToString()
    {
        StringBuilder res = new StringBuilder();
        Node cur = head;
        while (cur != null)
        {
            res.Append(cur + "->");//cur.ToString()
            cur = cur.next;
        }
        res.Append("Null");
        return res.ToString();
    }
}
